package cn.lbd.arithmetic.leetcode.editor.cn;
//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
//
// 你的算法时间复杂度必须是 O(log n) 级别。 
//
// 如果数组中不存在目标值，返回 [-1, -1]。 
//
// 示例 1: 
//
// 输入: nums = [5,7,7,8,8,10], target = 8
//输出: [3,4] 
//
// 示例 2: 
//
// 输入: nums = [5,7,7,8,8,10], target = 6
//输出: [-1,-1] 
// Related Topics 数组 二分查找 
// 👍 596 👎 0

import java.util.ArrayList;
import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution34 {
    private static int count = 1;
    public static int[] searchRange(int[] nums, int target) {
        if (nums == null) {
            return null;
        }
        int low = 0, high = nums.length - 1;
        int mid;
        int[] index = new int[nums.length];
        int i = 0;
        if (high - low == 1) {
            count++;
            if (nums[low] == target && nums[high] != target) {
                return new int[]{low};
            } else if (nums[high] == target && nums[low] != target) {
                return new int[]{high};
            } else if (nums[high] == nums[low] && nums[low] == target) {
                return new int[]{low, high};
            } else {
                return new int[]{-1, -1};
            }
        }
        while (low <= high) {
            if (low == high && nums[low] == target) {
                count++;
                index[i++] = low;
                return index;
            }
            mid = (low + high) / 2;
            while (nums[mid] == target) {
                index[i++] = mid;
                if (mid == 0) {
                    int z = 1;
                    while (nums[mid + z] == nums[mid]) {
                        count++;
                        index[i++] = mid + z;
                        z++;
                    }
                    return index;
                }
                if (nums[mid - 1] != target && nums[mid + 1] != target) {
                    return index;
                } else {
                    int k = 1;
                    while (mid - k >= 0 && mid + k <= high) {
                        if (nums[mid - k] == target) {
                            count++;
                            index[i++] = mid - k;
                        }
                        if (nums[mid + k] == target) {
                            count++;
                            index[i++] = mid + k;
                        }
                        k++;
                    }
                    return index;
                }

            }
            if (nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            }
        }
        return new int[]{-1, -1};
    }

    public static int[] change(int[] nums) {
        int temp[] =new int[count];
        for (int i = 0; i < count; i++) {
            temp[i] = nums[i];
        }
        Arrays.sort(temp);
        return temp;
    }

    public static void main(String[] args) {
        int nums[] = {5,5,5,5,5};
        int[] ints = change(searchRange(nums, 5));
        System.out.println(Arrays.toString(ints));
    }

}
//leetcode submit region end(Prohibit modification and deletion)
